//题目:
// 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
// k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
// 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换

#include<iostream>

using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    void ReverseList(ListNode* prev,ListNode* head,int size){
        if(size<=1)return;
        ListNode* newhead=head,*cur=head->next;
        while(size>1){
            //记录cur的下个结点位置
            ListNode* next=cur->next;
            //头插
            cur->next=newhead;
            newhead=cur;
            //更新cur、size
            cur=next,size--;
            //连接newhead->next，连接尾
            if(size==1)head->next=cur;
        }
        if(prev)prev->next=newhead;//连接头
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        int count=0;//计算链表总长度
        ListNode* cur=head,*newhead=head;
        while(cur){
            if(count==k-1)newhead=cur;
            cur=cur->next;
            count++;
        }
        //复位cur
        cur=head;
        int i=0;//反转过的结点数
        ListNode* prev=head;
        while(cur){
            if((count-i)/k>0){
                //找到k个结点后的结点next
                ListNode* next=cur;
                int t=k;
                while(t>0 && next)next=next->next,t--;
                //反转链表
                if(i==0)ReverseList(nullptr,cur,k);//从cur开始，反转k个结点
                else ReverseList(prev,cur,k);//从cur开始，反转k个结点
                //更新prev、cur、i
                prev=cur,cur=next,i+=k;
            }
            else break;
        }
        return newhead;
    }
};